package base

import (
	"gitee.com/chuanjinge/go-leet/tool"
)

// 背包最大容重量为4，现有物品的重量和价值分别为：
// 物品  重量  价值
//  0    1     15
//  1    3     20
//  2    4     30
// 问背包能背的最大价值是多少？

// 暴力解法
// 用递归+回溯的方法，尝试所有的可能性。记录最大价值，每次找到比较一下即可。
// 递归的出口是剩余容重量为负数了（跳出）和剩余容重量为0（参与比较）
// 递归的参数是：剩余容重量 和 剩余物品
// 递归的子问题是：从指定的剩余物品中向组合中添加一个小于剩余容重量的物品。
func FindByVoilence(goods [][]int, maxCap int) int {
	maxValue := 0     // 最大价值
	path := [][]int{} // 已添加的物品组合
	// 参数 start 表示goods集合的起始位置到最后位置构成的可用剩余物品
	// 参数 value 表示最大的剩余容重量
	var recursivewithbacktrace func(start int, cap int)
	recursivewithbacktrace = func(start int, cap int) {
		if start >= len(goods) {
			return
		}
		if cap >= 0 {
			sum := 0
			for _, p := range path {
				sum += p[1]
			}
			if sum > maxValue {
				maxValue = sum
			}
		} else {
			return
		}
		for i := start; i < len(goods); i++ {
			leftCap := cap - goods[i][0]
			path = append(path, goods[i])
			recursivewithbacktrace(i+1, leftCap)
			// 递归栈回来后再当前层级的栈中恢复最开始的状态
			path = path[:len(path)-1]
		}
	}
	recursivewithbacktrace(0, maxCap)
	return maxValue
}

// 以动态规划的方式解决该问题
//   - 动规的元素定义：dp[i][j] 表示从[0,i]个物品中填充容重量为j的背包可以得到的最大价值。
//   - 动规的状态转移规则：
//     如果我们不状态物品i，则最大价值就是 dp[i-1][j];
//     如果装填了物品i，就意味着我们要腾出物品i的容重量来，此时的最大价值应该是 dp[i-1][j-weight(i)] + value(i);
//     以上二者的最大值即是目标值!!!
//   - 动规的初始化：j为0是，不管什么i，最大价值都是0； i为0时，也就是说只有一个物品，j<weight(i)那么最大价值就是0，否则最大价值就是value(i)
//
// 遍历方式：
// 比较好理解的遍历方式是我们一点一点的增加物品，在指定的物品集合中再一点一点的增加容量
func FindByDP(goods [][]int, maxCap int) int {
	var dp [][]int
	// 有几个物品，我们就让dp的元素有几个
	dp = make([][]int, len(goods))
	// 每个元素是一个 []int{} 其长度是 maxCap
	for i := 0; i < len(goods); i++ {
		dp[i] = make([]int, maxCap+1)
		// 初始化
		dp[i][0] = 0
		// 初始化
		if i == 0 {
			for j := 0; j <= maxCap; j++ {
				if goods[0][0] > j {
					dp[i][j] = 0
				} else {
					dp[i][j] = goods[0][0]
				}
			}
		}
	}

	// 状态转移
	for i := 1; i < len(goods); i++ {
		for j := 1; j <= maxCap; j++ {
			// 非边缘位置
			// 1. 如果我们不状态物品i
			value1 := dp[i-1][j]
			// 2. 如果装填了物品i
			capEnough := j - goods[i][0]
			if capEnough < 0 {
				dp[i][j] = value1
			} else {
				value2 := dp[i-1][capEnough] + goods[i][1]
				dp[i][j] = tool.Max(value1, value2)
			}
		}
	}

	return dp[len(goods)-1][maxCap]
}
